package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: <a href="https://leetcode.cn/problems/generate-parentheses/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china">22. 括号生成</a>
 * @author: zhaoyinglin
 * @date: 2024/3/5
 */
public class GenerateParenthesis {

    public static void main(String[] args) {

        Solution solution = new Solution();

        System.out.println(solution.generateParenthesis(3));

    }

    static class Solution {
        public List<String> generateParenthesis(int n) {

            List<String> result = new ArrayList<>();

            if (n == 0) {
                return result;
            }

            dfs(result, 0, 0, n, "");

            return result;
        }

        private void dfs(List<String> result, int left, int right, int n, String s) {

            if (left == n && right == n) {
                result.add(s);
                return;
            }

            if (left < n) {
                dfs(result, left + 1, right, n, s + "(");
            }
            if (right < left && right < n) {
                dfs(result, left, right + 1, n, s + ")");
            }
        }

    }

}
